/* (c) Copyright 1993 by Joseph Felsenstein.
   Written by Joseph Felsenstein, Akiko Fuseki, Sean Lamont, and Andrew Keeffe.
   Permission is granted to copy and use this program provided no fee is
   charged for it and provided that this copyright notice is not removed. */

#include <map>
#include <string>
#include <vector>
//#include <ext/hash_map>
#include <tr1/unordered_map>

// component headers
#include "digest.h"
#include "matrix.h"
#include "string_hash.h"
#include "md4.h"

namespace kitsch_tree
{

struct hash_digest
{
std::size_t operator()(const t_digest& s) const
{
	return s.trunc_to32();
}
};

//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888

//	struct t_kitsch_node

//
enum eCHILD_NUM{CHILD_LEFT, CHILD_RITE, CHILD__ALL};
struct t_kitsch_tree;
struct t_reorder_node;
struct t_kitsch_node
{		  /* describes a leaf sequence or an internal branch node */
	friend struct t_kitsch_tree;
	friend struct t_reorder_node;
	friend struct do_create_kitsch_tree;
private:
	bool			leaf;
	unsigned		UID;		// per tree UIDs offset into shared memory
								// first leaves then nodes
public:
	enum eNODETYPE{eLEAF, eNON_LEAF};
	t_kitsch_node(unsigned count, t_kitsch_tree* tree_, eNODETYPE leaf_ = eLEAF) :
						leaf(leaf_ == eLEAF),
						UID(0),
						parent(0),
						tree(tree_),
						treepos(0),
						len_to_leaf(0.0),
						same_len_to_leaf(false),
						weight(0.0),
						processed(false),
						child_num(CHILD_LEFT)
	{
		clear();
	}
	void			clear ()			{	parent = children[0]  = children[1] = 0;}
	t_kitsch_node *	parent;				// same as phylip back for tips and main nodes
	t_kitsch_tree*	tree;
									// UID is unique for this node belong to each tree
									// is actually offset into tree's array of nodes
									// matrix and weights
	unsigned		get_UID()	const	{	return UID; 					}

	// used in replace_sub_tree and assignment. Bad idea?
	unsigned		treepos;			// offset into matrix and weights
	float			len_to_leaf;
	bool			same_len_to_leaf;	// bookkeeps scrunched nodes
	float			weight;				// weight of t_kitsch_node used by scrunch
	bool			processed;			// used by evaluate
	t_kitsch_node *	get_parent() const	{	return parent;					}
	t_kitsch_node *	children[2];		// same as phylip next->back for main nodes
										// same as phylip next->next->back for main nodes
	eCHILD_NUM		child_num;			// whether is left right or nth child of parent


	void			CHECK_LINKS() const;
	t_kitsch_node*	sibling() const;
	void			set_parent(t_kitsch_node* new_parent, eCHILD_NUM num);
	void			left_splice_below(t_kitsch_node& new_parent, t_kitsch_node& new_tip);
	t_kitsch_node& 	operator = (const t_kitsch_node& other);
	bool 			operator!= (const t_kitsch_node& other) const;
	bool 			operator== (const t_kitsch_node& other) const;
	bool			is_leaf() const				{	return leaf;					}
};

struct t_reorder_node
{
	bool	is_leaf;
	unsigned leaf_UID;
	unsigned left;
	unsigned rite;
	t_reorder_node(const t_kitsch_node& node) :
		is_leaf(node.is_leaf()), leaf_UID(node.UID)
	{
		if (!node.is_leaf())
		{
			// may be unused
			left = node.children[0] ? node.children[0]->UID : unsigned(-1);
			rite = node.children[1] ? node.children[1]->UID : unsigned(-1);
		}
	}
};

//

//	struct t_kitsch_node

//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888

//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888


//	t_kitsch_tree
//	=============


//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888
struct t_kitsch_tree
{
	unsigned		invalid_tree;		// used in evaluate
	typedef			t_kitsch_node 	t_node_type;
	
	//typedef __gnu_cxx::hash_map<t_digest, float, hash_digest> t_map_digest_float;
	typedef std::tr1::unordered_map<t_digest, float, hash_digest> t_map_digest_float;

	//typedef std::map<t_digest, float> t_map_digest_float;
	//initialize
	t_kitsch_tree(	bcpp_matrix::t_dense_matrix_f&				d,
					bcpp_matrix::t_dense_matrix_f&				w,
					const std::vector<std::string>&		names,
					float								power,
					t_progress_indicator& 				dots,
					unsigned							cnt_leaves_ = 0);
	t_kitsch_tree(	t_kitsch_tree other, t_node_type& from_node);
	void			replace_subtree(t_kitsch_tree other, t_node_type& from_node);
	t_kitsch_tree& 	operator = (const t_kitsch_tree& other);
	void			prepare_data();


	bcpp_matrix::t_dense_matrix_f&				d;
	bcpp_matrix::t_dense_matrix_f&				w;
	bcpp_matrix::t_dense_matrix_bool			nulls;
	const std::vector<std::string>&		names;
	float								power;
	unsigned 							cnt_leaves;
	unsigned 							cnt_nodes;
	unsigned							cnt_trees_examined;
	unsigned							cnt_non_null_data;
	std::vector<t_node_type>			shared_mem;
	std::deque<t_node_type*> 			nodes;
	mutable std::vector<t_reorder_node>	normalisation_nodes;
	unsigned 							recurse_reorder(unsigned parent_UID) const;

	float								sum_sqrs;
	t_node_type*						optimal_add_locus;
	bool								sum_sqrs_lowered;

	float								best_sum_sqrs;
	t_progress_indicator*				pdots;
	t_node_type*						root;
//	std::map<t_digest, float>			cached_evaluate_results;
	t_map_digest_float					cached_evaluate_results;
	unsigned							cnt_evaluate_cache_hits;


	void 			CHECK_LINKS() const;
	float			secondtraverse(							t_node_type& ll,
															t_node_type& kk,
															t_node_type& ii,
															t_node_type& jj);
	float			firstraverse(							t_node_type& q,
															t_node_type& r);
	float			sumtraverse(							t_node_type& q);
	void			evaluate();
	void			try_add(								t_node_type& where,
															t_node_type& item,
															t_node_type*& parent);
	void			recursive_find_optimal_add_locus(		t_node_type& where,
															t_node_type& item,
															t_node_type* parent);
	void			get_optimal_add_locus(					t_node_type& item,
															t_node_type* parent);
	void			try_rearrange(							t_node_type& item);
	void			recursive_find_optimal_rearrangement(	t_node_type& item);
	t_node_type*	remove(									t_node_type& item);
	void			rearrange();
	void			maketree(const std::vector<unsigned>& order_of_entry);
	void			maketree(const bcpp_tree::t_tree& orig_tree);
	std::string		to_str();
//	t_digest&		to_md4_hash(t_digest& hv){return md4_hash(to_str(), hv);}
	t_digest&		to_md4_hash(t_digest& hv)const;
	// defaults to root
	template <typename T> void for_each(T& t, t_node_type* = 0 );
	template <typename T> void for_each(T& t, const t_node_type* = 0) const;
	template <typename T> void recurse(T& t, t_node_type&);
	template <typename T> void recurse(T& t, const t_node_type&) const;
};


//________________________________________________________________________________________

//	for_each

//________________________________________________________________________________________
template <typename T> void t_kitsch_tree::for_each(T& t, t_node_type* from_node)
{
	t_node_type* p_node = from_node ? from_node : root;
	recurse(t, *p_node);
}

template <typename T> void t_kitsch_tree::for_each(T& t, const t_node_type* from_node) const
{
	const t_node_type* p_node = from_node ? from_node : root;
	recurse(t, *p_node);
}


template <typename T> void t_kitsch_tree::recurse(T& t, const t_node_type& curr_node) const
{
	t.pre_curse(curr_node);
	if (!curr_node.leaf)
	{
		recurse(t, *curr_node.children[CHILD_RITE]);
		recurse(t, *curr_node.children[CHILD_LEFT]);
	}
	t.post_curse(curr_node);
}

template <typename T> void t_kitsch_tree::recurse(T& t, t_node_type& curr_node)
{
	t.pre_curse(curr_node);
	if (!curr_node.leaf)
	{
		recurse(t, *curr_node.children[CHILD_RITE]);
		recurse(t, *curr_node.children[CHILD_LEFT]);
	}
	t.post_curse(curr_node);
}

}

